package leetcode.interviewClassics;

import leetcode.ListNode;

/**
 * @author Cheng Jun Description: 给定两个用链表表示的整数，每个节点包含一个数位。
 *     <p>这些数位是反向存放的，也就是个位排在链表首部。
 *     <p>编写函数对这两个整数求和，并用链表形式返回结果。 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 输出：2 -> 1 -> 9，即912
 *     https://leetcode-cn.com/problems/sum-lists-lcci/
 * @version 1.0
 * @date 2021/11/1 20:32
 */
public class addTwoNumbers1 {
  public static void main(String[] args) {

    // ListNode listNode2 = new ListNode(3);
    // ListNode listNode1 = new ListNode(4, listNode2);
    ListNode listNode0 = new ListNode(1, null);

    // ListNode listNode21 = new ListNode(4);
    ListNode listNode11 = new ListNode(9, null);
    ListNode listNode01 = new ListNode(9, listNode11);
    System.out.println(addTwoNumbers(listNode0, listNode01));
  }

  // 迭代解法：将 l1 和 l2 同时往后移动，直到两者都为null 且 不进1 时，迭代停止
  static ListNode addTwoNumbers0(ListNode l1, ListNode l2) {
    // l1 = [2,4,3], l2 = [5,6,4]
    // [7,0,8] 342 + 465 = 807.
    int jin1 = 0;
    ListNode head = new ListNode();
    ListNode tail = head;
    while (l1 != null || l2 != null || jin1 != 0) {
      if (l1 != null) {
        jin1 += l1.val;
        l1 = l1.next;
      }
      if (l2 != null) {
        jin1 += l2.val;
        l2 = l2.next;
      }
      tail.next = new ListNode(jin1 % 10);
      tail = tail.next;
      jin1 /= 10;
    }
    return head.next;
  }

  // (7 -> 1 -> 6) + (5 -> 9 -> 2)，即 7 + 5 后 进一，然后 1->6 + 9 -> 2
  static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode ans = new ListNode(0);
    addTwoNumber(l1, l2, 0, ans);
    return ans.next;
  }

  // 同时 往后走 next ，l1 l2都为null 且 jin1 为0 return, 否则就递归。
  private static void addTwoNumber(ListNode l1, ListNode l2, int jin1, ListNode tail) {
    if (l1 == null && l2 == null && jin1 == 0) return;
    if (l1 != null) {
      jin1 += l1.val;
      l1 = l1.next;
    }
    if (l2 != null) {
      jin1 += l2.val;
      l2 = l2.next;
    }
    ListNode listNode = new ListNode(jin1 % 10);
    jin1 = jin1 >= 10 ? 1 : 0;
    tail.next = listNode;
    addTwoNumber(l1, l2, jin1, tail.next);
  }
}
